package com.lambdademo;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

@Slf4j
public class Solution {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4};
        int[] profit = new Solution().productExceptSelf(nums);
        log.info("result:{}", profit);
    }

    //给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
    //题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
    //请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] leftProducts = new int[n];
        int[] rightProducts = new int[n];
        int[] result = new int[n];

        // 初始化前缀积数组
        leftProducts[0] = 1;
        for (int i = 1; i < n; i++) {
            leftProducts[i] = leftProducts[i - 1] * nums[i - 1];
        }

        // 初始化后缀积数组
        rightProducts[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            rightProducts[i] = rightProducts[i + 1] * nums[i + 1];
        }

        // 计算结果数组
        for (int i = 0; i < n; i++) {
            result[i] = leftProducts[i] * rightProducts[i];
        }

        return result;
    }


    //给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
    //根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，
    // 并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。
    public int hIndex(int[] citations) {
        Arrays.sort(citations); // 将数组排序
        int n = citations.length;
        for (int i = 0; i < n; i++) {
            int h = n - i; // 计算当前的 h 值
            if (citations[i] >= h) {
                return h; // 找到最大的 h
            }
        }
        return 0; // 如果没有找到符合条件的 h，返回 0
    }

    //给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
    //每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
    //0 <= j <= nums[i]
    //i + j < n
    //返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
    public int jump(int[] nums) {
        int jumps = 0;
        int currentEnd = 0;
        int farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }
        return jumps;
    }

    //给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
    //判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
    public boolean canJump(int[] nums) {
        int maxReach = 0; // 初始化最远可达位置为0
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) { // 如果当前位置i大于最远可达位置，返回false
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]); // 更新最远可达位置
        }
        return true; // 如果遍历完整个数组，返回true
    }

    //给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
    //在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
    //返回 你能获得的 最大 利润 。
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int buyIn = prices[0];
        boolean isBuy = true;
        for (int i = 1; i < prices.length; i++){
            if (prices[i] < buyIn && isBuy){
                buyIn = prices[i];
            }else if (prices[i] > buyIn && isBuy){
                maxProfit += prices[i] - buyIn;
                isBuy = false;
            } else if (!isBuy) {
                isBuy = true;
                buyIn = prices[i];
            }
        }
        return maxProfit;
    }
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n; // 处理 k 大于数组长度的情况

        // 反转整个数组
        reverse(nums, 0, n - 1);
        // 反转前 k 个元素
        reverse(nums, 0, k - 1);
        // 反转剩余的元素
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums){
            if (map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else{
                map.put(num, 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
            if (entry.getValue() > nums.length / 2){
                return entry.getKey();
            }
        }
        throw new IllegalArgumentException("majority element not found");
    }

    //给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
    //不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
    public int removeDuplicates(int[] nums) {
        int currentNum = 0;
        int temp = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++){
            if (nums[i] != temp){
                nums[++currentNum] = nums[i];
                temp = nums[i];
                count = 1;
            }else if (nums[i] == temp && count < 2){
                nums[++currentNum] = nums[i];
                count++;
            }
        }
        return currentNum + 1;
    }
    public int removeDuplicates1(int[] nums) {
        int currentNum = 0;
        int k = 1;
        int temp = nums[0];
        for (int i = 1; i < nums.length; i++){
            if (nums[i] != temp){
                nums[++currentNum] = nums[i];
                temp = nums[i];
                k++;
            }
        }
        return k;
    }
    public int removeElement(int[] nums, int val) {
        int total = 0;
        int currentNum = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != val){
                nums[currentNum++] = nums[i];
            }else{
                total++;
            }
        }
        return total;
    }
}
